/*
container/heap

二叉排序树是为了实现动态查找而涉及的数据结构，它是面向查找操作的，在二叉排序树中查找一个节点的平均时间复杂度是O(logn)；
在堆中搜索并不是第一优先级，堆是为了实现排序而实现的一种数据结构，它不是面向查找操作的，因为在堆中查找一个节点需要进行遍历，其平均时间复杂度是O(n)。

资料
https://www.freesion.com/article/2791612000/
https://blog.csdn.net/Zj_boring/article/details/105157360
*/
package main

import (
	"container/heap"
	"fmt"
)

type Intheap []int

func (h Intheap) Len() int           { return len(h) }
func (h Intheap) Less(i, j int) bool { return h[i] < h[j] }
func (h Intheap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *Intheap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *Intheap) Pop() interface{} {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[:n-1]
	return x
}

func main() {

	nums := &Intheap{2, 5, 3, 9, 4, 6, 8}
	heap.Init(nums)
	fmt.Println(nums) // [2 4 3 9 5 6 8]
	heap.Push(nums, 1)
	fmt.Println(nums) //[1 2 3 4 5 6 8 9]
	heap.Push(nums, 3)
	fmt.Println(nums) // [1 2 3 3 5 6 8 9 4]

	heap.Remove(nums, 4)
	fmt.Println(nums) //[1 2 3 3 4 6 8 9]

	(*nums)[1] = 10
	fmt.Println(nums) //[1 10 3 3 4 6 8 9]
	heap.Fix(nums, 1)
	fmt.Println(nums) //[1 3 3 9 4 6 8 10]

	x := heap.Pop(nums) //1
	fmt.Println(x)

}
